COMMENT ⊗   VALID 00007 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002
C00003 00003		1. a.  In terms of the quality of solutions  found,  and  the
C00006 00004		2.   The unbounded unit-preference strategy is: "compute the
C00009 00005		3.  After reading the speech report for inspiration, you have
C00012 00006		4.  Consider the following variant  of  the  missionary   and
C00015 00007		5.  One of the central problems in the recognition of  scenes
C00016 ENDMK
C⊗;









                         STANFORD UNIVERSITY


                     COMPUTER SCIENCE DEPARTMENT


                            April 1, 1972










                    Ph.D. QUALIFYING EXAMINATION



                       Artificial Intelligence









The examination will be open book.  The first session will be from
9:30 to 12:30 pm, and the second session will be from 1:30 to 4:30
pm.  No work on the examination will be done during the lunch break.

	1. a.  In terms of the quality of solutions  found,  and  the
efficiency  with  which solutions are produced, the Heuristic DENDRAL
program is one of the most powerful heuristic programs in  existence.
What is the primary source of this problem-solving power?

	b.   In  his  paper on Heuristic Programming, subtitled "Ill-
Structured Problems",  Newell  introduces  concepts  and  terminology
intended to categorize and describe heuristic programs.  Use Newell's
concepts and terminology to describe Heuristic DENDRAL.

	c.  What are the purposes of having  a  systematic  generator
(the DENDRAL algorithm) at the heart of Heuristic DENDRAL?

	d.  We use heuristic processes to achieve search reduction in
administering the search for a solution to a problem.  How  does  the
heuristic   process   known  as  the  Planner  in  Heuristic  DENDRAL
contribute its heuristic power to search  reduction?   Illustrate  by
making  reference to some of the results in the results tables of the
DENDRAL paper you were asked to read.  From a heuristic search  point
of  view,  how  does  "planning" in DENDRAL differ from "planning" as
this method has been discussed elsewhere in the A.I. literature (e.g.
the Planning Method of GPS, Hewitt's Planner, Robot Planning)?

	e.   You  were  asked  to  read a paper by Amarel in which he
disucsses representation of knowledge and  shift  of  representation.
How  has  this  problem  been  studied  in  the  context  of the task
environment of Heuristic DENDRAL?  What are the results?
	2.   The unbounded unit-preference strategy is: "compute the
resolvents of all unit clauses with every clause before computing the
resolvents of any pair of non-units".

The  input  clause  strategy is: "compute the resolvents of a pair of
clauses only if one of them is a member of the initial set of clauses
(i.e. an axiom or the negation of the theorem)".

	a.   Give  examples showing that both of these strategies are
logically incomplete.


	A  replacement  rule of inference for equality may be defined
as follows.

	Let E be the equality predicate and s, t, u be terms.  Let  A
and  B  be clauses with no variables in common such that A contains a
positive equality atom, either A = E(s,t)∨A' or  A=E(t,s)∨A',  and  a
term  u occurs at least once in B.  (Note: u may occur as a subterm).
Let s and u have a common substitution instance, and suppose that α a
most  general  unifier  such  that  sα=uα.   Let  B* be the result of
replacing an occurrence of uα in Bα by tα.    Let  C  be  the  clause
A'α∨B*.  Then C may be inferred by replacement from A into B.  Denote
the set of such inferences by P(A,B).
	If A and B have common variables, these must be eliminated by
a change of variables before the rule is applied.


	b.  For all A and B, is P(A,B)=P(B,A)?  Prove your answer.


	c.  Let A be E(f(x,g(x)),e) and B be  E(f(x,x),e).   Compute
P(A,B) and P(B,A).



	d.  PROVE:  For any C that can be inferred by replacement
from A and B there is a C' satisfying (i) C' implies C, and (ii)
C' is obtained by a sequence of resolutions from the set consisting
of A, B, and the axioms for equality.


[section (d) of this question was omitted from the actual examination
on April 1, 1972]
	3.  After reading the speech report for inspiration, you have
accepted  a consulting job with the linguistics department to predict
the feasibility of a speech understanding system.  You are given  the
following  vocabulary  and grammar.  You want a computer to recognize
semantically and syntactically legal sentences.  The  department  did
not specify the semantics but any reasonable assumptions will do.

The vocabulary is:

	programs, monkeys, termites,
	search, climb, eat
	trees, bits, bananas

The grammar is:

	S → SUBJECT VERB OBJECT
	SUBJECT → programs, monkeys, termites
	VERB → search, climb, eat
	OBJECT→ trees, bits, bananas

a.	First, assume a probability of correct recognition of one  of
the  vocabulary  words, when isolated, to be .7.  Suppose the lexical
segmentation scheme is perfect.  Without  use  of  the  grammar  what
correct   string  recognition  rate  (all  words  correct)  might  be
expected on three-word strings?

b.	Based on the results of  the  speech  report  how  might  the
probability of word-confusion error depend on vocabulary size?

c.	Make  a  reasonable  assumption (either your answer to (2) or
some other guess) of the effect of  vocabulary  size  on  recognition
rate.   State  your assumption.  Now, using the grammar, but still no
semantics, what correct string recognition rate  might  be  expected?
(rough calculations are fine).

d.	Specify  your  assumed semantically meaningful strings.  Show
precisely why the recognition rate  is  better.    For  extra  credit
calculate  an  expected  correct 3-word string recognition rate using
both syntax and semantics.


	4.  Consider the following variant  of  the  missionary   and
cannibals problem:

	"Three  missionaries and three cannibals come to a river that
they wish to cross.  They find a boat that holds two people  and  can
be  rowed  by one or two.  However, if one person rows by himself, he
will be too tired to row by himself again.    Besides  that,  if  the
cannibals  ever  outnumber  the  missionaries  on  either bank of the
river, the missionaries will be eaten.  How can they all safely cross
the river?"

	a. Write a LISP program to find a solution.

	b. Write a micro-PLANNER program to find a solution.

	c.  Write  a  situation-calculus description of the situation
and the effects of actions from which it  follows  that  there  is  a
solution.    The   "result"   formalism  of  McCarthy  and  Hayes  is
recommended.

	d. Discuss the problem of making a program that could go from
the  above  English statement of the missionary and cannibals problem
to a LISP program for doing  the  tree  search.   Would  the  PLANNER
formalism  or  the  McCarthy  and  Hayes  formalism  be  suitable  as
intermediate steps.  Why or why not?  In so far as  possible,  divide
the   overall   problem   into  sub-problems  that  might  be  solved
independently.

	5.  One of the central problems in the recognition of  scenes
involving  plane-bounded  objects is the segmentation problem.  Falk,
in his thesis, suggests improvements to Guzman's algorithm.  Describe
Guzman's  and  Falk's  algrorithms.   Give  an example different from
those in Falk's thesis where  Guzman's  fails  and  Falk's  succeeds.
Give an example where they both fail.

Extra credit: 
	a. Extend Falk's algorithm to cover the  case  you  presented
above.   If the new algorithm doesn' cover all cases, find a counter-
example.

	b. Discuss the segmentation problem for curved objects.